//
//  ProblemMS1002.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/3/24.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 面试题 10.02. 变位词组 【字符串转换】【哈希】
 编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。

 注意：本题相对原题稍作修改

 示例:
 输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
 输出:
 [
   ["ate","eat","tea"],
   ["nat","tan"],
   ["bat"]
 ]
 说明：
 所有输入均为小写字母。
 不考虑答案输出的顺序。
 */
@objcMembers class ProblemMS1002: NSObject {
    func solution() {
        print(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
    }
    
    /*
     一：将字符串转换成01001020（26个）的形式
     1: 遍历字符串数组，for str in strs {}
     2: 创建一个数组charts[26] = [0]
     3: 遍历str，遇到字符，就把它对于的位置+1
     4: 这样每个字符串 都对应一个26位的字符串
     二：哈希
     1: 创建一个字典，dic[String: Int]
     2: 步骤4生产的字符串，超找对应的位置，如果不存在，则创建一个数组 dic[str] = dic.count
     */
    func groupAnagrams(_ strs: [String]) -> [[String]] {
        var dic:[String: Int] = [:]
        
        var result:[[String]] = []      // 存储结果
        
        for str in strs {
            var charts = Array(repeating: 0, count: 26)
            for c in str {
                charts[Int(c.asciiValue!) - 97] += 1
            }
            let pStr = charts.reduce("") { (s, i) -> String in
                return s + String(i)
            }
            
            if dic[pStr] == nil {
                result.append([str])
                dic[pStr] = dic.count
            } else {
                result[dic[pStr]!].append(str)
            }
        }
        
        return result
    }
}
